package com.duoduo.algs4.Fundamentals;

import java.io.IOException;
import java.util.Arrays;

import com.duoduo.algs4.util.ArrayUtil;

import edu.princeton.cs.introcs.In;
import edu.princeton.cs.introcs.StdOut;

public class RemoveDuplicateElement {
	// 删除重复元素

	// 步骤1：排序
	// 步骤2：二分搜索[i+1,...n]
	// 步骤3：如果不存在，加入新数组，如果存在，go next
	public static int[] removeDuplicateElement(int[] a) {
		int M = a.length;
		if (M <= 0) {
			return null;
		}
		int[] b = new int[M];
		int index = 0;

		int hi = M - 1;
		int lo, key;
		for (int i = 0; i < M; i++) {
			lo = i + 1;
			key = a[i];
			if (-1 == BinarySearch.rank(key, a, lo, hi)) {
				b[index++] = key;
			}

		}
		// 剔除掉0
		int[] result = b;
		if (index < M) {
			result = new int[index];
			for (int i = 0; i < index; i++) {
				result[i] = b[i];
			}
			b = null;
		}
		return result;

	}

	public static void testConsole(String whiteListName) {
		StdOut.println("console");
		int[] whiteList = In.readInts(whiteListName);

		Arrays.sort(whiteList);
		int[] afterRemove = removeDuplicateElement(whiteList);
		StdOut.println("print");
		StdOut.println(whiteList.length);
		StdOut.println(afterRemove.length);
		
//		ArrayUtil.printArray(whiteList);
//		ArrayUtil.printArray(afterRemove);
	}

	public static void main(String[] args) {
		testConsole(args[0]);
	}

}
